今日題目

題目連結：1. Two Sum
題目主題：Array, Hash Table

簡單說說 Hash Table

Hash Table 主要的核心概念是使用 Key 去快速找到需要的 Value，而這個 Key 是用資料經過計算之後得到的值，通常是用 Hash Function 來得到一個值來當作 Key。

另外 Hash Table 也可以當作分類的方式來使用，前一篇有提到 Hash Functioin 要小心碰撞 (Collision) 的問題，但在這邊是刻意使用 Collision 來當作分類使用，下面是一個 Hash Table 用姓氏當範例：

這邊可以看到，是用姓氏的第一個字來當做 Key ，當中如果 Value 有多個的狀況是因爲出現碰撞的況狀，所以分類到同一個 Key 裡面。搜尋時也只要拿姓氏的第一個英文字母，就可以很快的搜尋到目標是否有在這個表裡面。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給一個 nums 數字陣列及一個 target 目標值，目的是要在 nums 之中找到可以相加成 target 的兩個數字，最終回傳這兩個數字的位置。

可以假設在答案一定只有一個的情況下去找出這兩個數字，另外 nums 中一個值只能使用一次。

約束：

• 2 <= nums.length <= 10的4次方
• -10的9次方 <= nums[i] <= 10的9次方
• -10的9次方 <= target <= 10的9次方
• 只會有一個答案在 nums 中

範例1

輸入: nums = [2,7,11,15], target = 9
輸出: [0,1]
解說: nums[0]是2, nums[1]是7， 2 + 7 = 9，最後輸出[0, 1].

範例2

輸入: nums = [3,2,4], target = 6
輸出: [1,2]
解說: nums[1]是2, nums[2]是4， 2 + 4 = 6，最後輸出[1, 2].

範例3

輸入: nums = [3,3], target = 6
輸出: [0,1]
解說: nums[0]是3, nums[1]是3， 3 + 3 = 6，最後輸出[0, 1].

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告一個 map 來實作 Hash Table。
2. 跑一個迴圈，每一圈處理的內容有：
   • 確認目前的數字是否有在map的key中，若有出現代表找到可加總成target的兩個數字位置，直接回傳這兩個位置結束。
   • 將（taget - 目前的數字）當作是map的key，位置(index)當value。

圖解過程

範例： nums = [2, 11, 15, 8, 4], target = 10

上圖是迴圈在跑的過程，下方的圓角長方是一個Hash Table，每一圈都會拿一個數字來確認是否有出現在 Hash Table 中。

step1 ~ step3 是沒有出現在 Hash Table 的狀況，所以會將 target - 目前的數字當作 key，位置（index）當 value。

step4 的 8 有在 Hash Table 中找到，代表有找到兩個數字加起來等於 taget 的兩個位置，最後將回傳這個 value 0 及目前的位置 3 結束。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Hash Table
        map = {}
        for i in range(len(nums)):
            # 若目前的數字已經進到 map 
            # 代表找到可加總成target的兩個數字位置
            if nums[i] in map:
                return [map[nums[i]], i]
            # 將（taget - 目前的數字）當作是map的key，位置當value
            key = target - nums[i]
            map[key] = i

希望您今天能瞭解到...

1. Hash Table 的基本概念
2. 1. Two Sum 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：653. Two Sum IV - Input is a BST